package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * 希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，
 * 也称为递减增量排序算法，同时该算法是冲破 O(n²) 的第一批算法之一。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
 * 待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。
 * <p>
 * 算法步骤我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2，缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示，{n/2, (n/2)/2, ..., 1}，称为增量序列。
 * 希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
 * 此处我们做示例使用希尔增量。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
 * <p>
 * 具体算法描述：
 * - 选择一个增量序列 {t1, t2, …, tk}，其中 (ti>tj, i<j, tk=1)；
 * - 按增量序列个数 k，对序列进行 k 趟排序；
 * - 每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 * <p>
 * 图解算法
 * 原始数组长度为10，如下所示
 * 6 4 5 7 2 8 3 0 9 1
 * 初始增量设为gap=Length/2=5,整个数组会被分为5个子数组分别为[6,8][4,3][5,0][7,9][2,1]
 * <p>
 * 分别对这5组进行直接插入排序，可以看到各组内部元素已有序之后缩小增量为gap=5/2=2,数组会被重新分为2个子数组分别为 [6,0,1,4,9][3,7,8,5,2]
 * <p>
 * 对以上两组数组再分别进行插入排序，数组变得更加有序，我们再缩小增量为gap=2/2=1,此时即为常规插入排序，整个数组为一组[0,2,1,3,4,5,6,7,9,8]
 * <p>
 * 可以看出数组已基本有序
 * 此时插入排序算法仅需少次微调即可完成排序
 *
 * @author Api
 * @date 2022/11/19 10:15
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 1, 4, 5, 2, 12, 4, 56, 2, 1};
        int[] ints = shellSort(arr);
        System.out.println(Arrays.toString(ints));
    }


    public static int[] shellSort(int[] arr) {
        int n = arr.length;
        int gap = n >> 1;
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int current = arr[i];
                int preIndex = i - gap;
                //插入排序,微调
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = current;
            }
            gap /= 2;
        }
        return arr;
    }
}
